package com.mzy.linear_struct.ks;

/**
 * @Author: mizy3
 * @Date: 2024/08/22/上午10:31
 * @Description:
 */
public class 数组中第K个最大元素 {
    // public int findKthLargest(int[] nums, int k) {
    //     // 1. 对数组进行原地建堆
    //     for (int i = nums.length / 2 - 1; i >= 0; i--) {
    //         heapifyDown(nums, i, nums.length);
    //     }
    //
    //     // 2. 获取前 k 个最大的元素
    //     int ans = nums[0];
    //
    //     for (int i = nums.length - 1; i >= 0 && --k > 0; i--) {
    //         ans = nums[0];
    //         swap(nums, 0, i);
    //         heapifyDown(nums, 0, i);
    //     }
    //     return ans;
    // }

    public int findKthLargest(int[] nums, int k) {
        for (int i = nums.length - 1; i >= 0; i--) {
            heapifyDown(nums, i, nums.length);
        }

        int ans = 0;
        for (int i = 0; i < k; i++) {
            ans = nums[0];
            swap(nums, 0, nums.length - i - 1);
            heapifyDown(nums, 0, nums.length - i - 1);
        }
        return ans;
    }


    private void heapifyDown(int[] arr, int index, int length) {
        while (index * 2 + 1 < length) {
            int left = index * 2 + 1;
            int right = index * 2 + 2;
            int large = left;

            if (right < length && arr[large] < arr[right]) {
                large = right;
            }

            if (arr[large] <= arr[index]) {
                break;
            }

            swap(arr, index, large);
            index = large;
        }
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}





















